The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
When data is sent across a communications channel, noise and other distortions of the channel may alter the data by the time the data is received. Various error detection and error correction mechanisms are used to detect and possibly correct such errors. One class of error correcting codes (ECC) is linear block ECCs, which include low-density parity check (LDPC) codes.
When using an LDPC code, user data is divided into blocks of K bits or symbols. Each of the blocks is mapped, or encoded, into a codeword having N bits or symbols, where N is greater than K. The difference between N and K represents redundancy. More redundancy allows for detection of errors even when more errors are present, and allows for more errors to be corrected. LDPC codes may be characterized by a rate calculated by dividing K by N.
FIG. 1 illustrates a graphical illustration of a simple ECC scheme. In FIG. 1, K is equal to four and N is equal to seven. A column 100 shows the 16 (24) possible combinations of user message bits. Column 104 shows 16 corresponding codewords. In this example, each codeword is created by prepending three parity bits to the user message bits. This encoding is performed at a transmitter, and the encoding is known a priori by the receiver.
For purposes of illustration only, one of the codewords (1101000) is transmitted across a channel 108. For example only, the resulting received data is 1111000. In this particular example, the third bit has been corrupted by the channel 108, switching from a zero to a one. This seven-bit data is part of a seven-bit word space 112, which represents all possible combinations of seven bits (27=128). However, only 16 of those seven-bit combinations are valid codewords.
A decoding process therefore determines which codeword of a seven-bit codeword space 116 corresponds to the received data. At various times, the received data may already be within the seven-bit codeword space 116. This can happen when a codeword is received uncorrupted by the channel 108. However, this may also occur if multiple bits of the codeword are corrupted by the channel 108, but the result is another valid codeword. In such a situation, the ECC may not detect an error. For this reason, as described in more detail below, a secondary error detection strategy, such as a cyclic redundancy check (CRC), may be used across multiple blocks of user data. Error detection mechanisms, such as CRC, are designed such that even multiple bit corruptions will still be detected. The trade off is that such CRC mechanisms may not be able to correct those errors. However, when an uncorrectable error is detected, the original data may be able to be retransmitted.
Once a valid seven-bit codeword is selected based on the received data, corresponding user bits from a four-bit message space 120 are determined by a decoding process. In the example of FIG. 1, a seven-bit codeword can be converted into a four-bit message simply by ignoring the left three bits of the seven-bit codeword.
In practice, ECC encoding may not simply prepend or append parity bits to user data to generate codewords. For example, such as in LDPC coding, a vector of user data may be multiplied by a generator matrix in order to arrive at a codeword. This may be represented as v=u·G, where u is user data to be encoded, G is the generator matrix, and v is the resulting codeword. Because the user data u is a block of K bits or symbols, and the resulting codeword v contains N bits or symbols, the generator matrix has K rows and N columns:
  G  =      [                                        g            00                                                g            01                                    …                                      g                          0              ,                              n                -                1                                                                                      g            10                                                g            11                                    …                                      g                          1              ,                              n                -                1                                                                          …                          …                          …                          …                                                  g                                          k                -                1                            ,              0                                                            g                                          k                -                1                            ,              1                                                …                                      g                                          k                -                1                            ,                              n                -                1                                                          ]  
A parity check matrix H is associated with a generator matrix G, and has the property that if the resulting codeword v was created by the generator matrix G, then the product of resulting codeword v and the transpose of the parity check matrix H is zero: v·HT=0. However, if a corrupted codeword is multiplied by the transpose of the parity check matrix H, a non-zero vector, called a syndrome, results: {circumflex over (v)}·HT=S. The LDPC decoding process attempts to find a codeword v′ based on the corrupted codeword that will cause the syndrome to go to zero, thereby indicating that the codeword v′ is a valid codeword. The codeword v′ may also be referred to as a hard decision, which may change throughout the course of LDPC decoding.
In a binary LDPC code, the user data and the codeword are expressed as binary bits. In non-binary LDPC encoding, the user message and the codewords are formed of non-binary symbols. For example only, the symbols may be chosen from a Galois Field (GF). For example, the symbols may be chosen from a GF-4 space. When user data is binary, the binary user data is first mapped into the GF-4 space. Similarly, decoded codewords are mapped from the GF-4 space back into the binary space. The elements of GF-4 may be called 0, 1, A, and B or, as below, 0, 1, 2, and 3. For reference only, addition and multiplication tables for GF-4 are presented here.
Add0123001231103 22230 133210
Multiply012300000101232023130312
An example generator matrix for creating a seven-symbol codeword from a four-symbol data vector is shown for purposes of illustration only:
      G    =          [                                    3                                1                                0                                2                                0                                0                                0                                                0                                1                                1                                0                                2                                0                                0                                                1                                1                                1                                0                                0                                2                                0                                                1                                0                                1                                0                                0                                0                                2                              ]        ,and the corresponding parity check matrix is:
  H  =      [                            2                          0                          0                          3                          0                          1                          1                                      0                          2                          0                          1                          1                          1                          0                                      0                          0                          2                          0                          1                          1                          1                      ]  
For an example four-symbol data vector, the codeword is calculated by multiplying the user data vector by the generator matrix. The resulting codeword v is checked by observing that multiplication of codeword by the transpose of the parity check matrix H is equal to zero:u=(1 3 0 2)v=u·G=(1 2 1 2 1 0 3)v·HT=0By contrast, if a corrupted codeword is received, such as when the last symbol of the codeword is received as a one instead of a three, the resulting multiplication by the transpose of the parity check matrix H is non-zero:{circumflex over (v)}=(1 2 1 3 1 0 1){circumflex over (v)}·HT=(1 1 2)Therefore, LDPC decoding attempts to find a codeword v corresponding to v′ that will cause the parity check multiplication to equal zero.